#ifndef MNOQUE_H_
#define MNOQUE_H_

#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

namespace lxj
{

constexpr size_t BASE = 10;
// 返回number在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline constexpr size_t bits(T number)
{
    size_t ans = 0;
    while (number > 0) {
        number /= BASE;
        ans++;
    }
    return ans;
}

// 基数排序核心代码
// 数据必须为非负整数
// bits是元素中最大值在BASE进制下有几位
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void r_sort(T* arr, size_t size, size_t bits)
{
    std::vector<T> help(size);
    size_t         cnt[BASE] = {};
    for (size_t offst = 1; bits > 0; offst *= BASE, bits--) {
        for (auto& i : cnt) {
            i = 0;
        }
        for (auto p = arr; p != arr + size; p++) {
            cnt[(*p / offst) % BASE]++;
        }
        for (int i = 1; i < BASE; i++) {
            cnt[i] = cnt[i] + cnt[i - 1];
        }

        for (int i = size - 1; i >= 0; i--) {
            const size_t index = --cnt[(*(arr + i) / offst) % BASE];
            help[index]        = *(arr + i);
        }
        for (T *p1 = arr, *p2 = help.data(); p1 != arr + size; p1++, p2++) {
            *p1 = *p2;
        }
    }
}

// 基数排序对数据有要求
// 必须为整数
template<class T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>, int> = 0>
inline void radix_sort(T* arr, size_t size)
{
    if (size == 0) return;
    T min = *std::min_element(arr, arr + size);
    for (T* p = arr; p != arr + size; p++) {
        *p -= min;
    }
    T max = *std::max_element(arr, arr + size);
    r_sort(arr, size, bits(max));
    for (T* p = arr; p != arr + size; p++) {
        *p += min;
    }
}
}   // namespace lxj

namespace lxj
{
// 和至少为K的最短子数组
// 给定一个数组arr，其中的值有可能正、负、0
// 给定一个正数k
// 返回累加和>=k的所有子数组中，最短的子数组长度
// 测试链接 : https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/
inline int shortestSubarray(std::vector<int>& nums, int k)
{
    constexpr int             MAXN        = 100001;
    static unsigned long long sum[MAXN]   = {};
    static int                deque[MAXN] = {};
    int                       h = 0, t = 0;

    constexpr int MAX = ~(1 << 31);
    int           ans = MAX;
    int           len = nums.size();
    std::partial_sum(nums.cbegin(), nums.cend(), sum + 1);
    /* for (int i = 0; i < len; i++) {
        sum[i+1]=sum[i]+nums[i];
    } */
    for (int r = 0; r <= len; r++) {
        while (h < t && sum[r] - sum[deque[h]] >= k) {
            ans = std::min(ans, r - deque[h++]);
        }
        while (h < t && sum[deque[t - 1]] >= sum[r]) {
            t--;
        }
        deque[t++] = r;
    }
    return ans == MAX ? -1 : ans;
}

// 满足不等式的最大值
// 给你一个数组 points 和一个整数 k
// 数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序
// 也就是说 points[i] = [xi, yi]
// 并且在 1 <= i < j <= points.length 的前提下，xi < xj 总成立
// 请你找出 yi + yj + |xi - xj| 的 最大值，
// 其中 |xi - xj| <= k 且 1 <= i < j <= points.length
// 题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
// 测试链接 : https://leetcode.cn/problems/max-value-of-equation/
inline int findMaxValueOfEquation(std::vector<std::vector<int>>& points, int k)
{
    constexpr int              MAXN        = 100001;
    static std::pair<int, int> deque[MAXN] = {};
    int                        h = 0, t = 0;

    constexpr int MIN = 1 << 31;
    int           ans = MIN;
    for (int i = 0; i < points.size(); i++) {
        int x = points[i][0];
        int y = points[i][1];
        while (h < t && deque[h].first + k < x) {
            h++;
        }
        if (h < t) {
            ans = std::max(ans, x + y + deque[h].second - deque[h].first);
        }
        while (h < t && deque[t - 1].second - deque[t - 1].first <= y - x) {
            t--;
        }
        deque[t].first    = x;
        deque[t++].second = y;
    }
    return ans;
}

// 你可以安排的最多任务数目
// 给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成
// 需要的力量值保存在下标从 0 开始的整数数组 tasks 中，
// 第i个任务需要 tasks[i] 的力量才能完成
// 每个工人的力量值保存在下标从 0 开始的整数数组workers中，
// 第j个工人的力量值为 workers[j]
// 每个工人只能完成一个任务，且力量值需要大于等于该任务的力量要求值，即workers[j]>=tasks[i]
// 除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength
// 你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸
// 给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength
// 请你返回 最多 有多少个任务可以被完成。
// 测试链接 : https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/
inline int maxTaskAssign(std::vector<int>& tasks,
                         std::vector<int>& workers,
                         int               pills,
                         int               strength)
{
    auto f = [&tasks, &workers](int tl, int tr, int wl, int wr, int s, int pills) {
        int        h = 0, t = 0;
        int        cnt          = 0;
        static int deque[50001] = {};

        for (int i = wl, j = tl; i <= wr; i++) {
            for (; j <= tr && tasks[j] <= workers[i]; j++) deque[t++] = j;
            if (h < t && tasks[deque[h]] <= workers[i]) {
                h++;
            }
            else {
                for (; j <= tr && tasks[j] <= workers[i] + s; j++) deque[t++] = j;
                if (h < t) {
                    cnt++;
                    t--;
                }
                else {
                    return false;
                }
            }
        }
        return cnt <= pills;
    };

    int tsize = tasks.size(), wsize = workers.size();
    lxj::radix_sort(tasks.data(), tsize);
    lxj::radix_sort(workers.data(), wsize);

    int ans = 0;
    for (int l = 0, r = std::min(tsize, wsize), m; l <= r;) {
        m = l + (r - l) / 2;
        if (f(0, m - 1, wsize - m, wsize - 1, strength, pills)) {
            ans = m;
            l   = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}
}   // namespace lxj

#endif